package m_HashTable;

import java.util.TreeMap;

public class HashTable__1<K, V> {

    private TreeMap<K, V>[] hashtable;
    private int size;
    private int M; //容量

    public HashTable__1(int M){
        this.M = M;
        size = 0;
        hashtable = new TreeMap[M];  //开接口 肯定能放TreeMap<K, V>  数组间没有父子关系  object[]并不是数组的父类 
        for(int i = 0 ; i < M ; i ++)
            hashtable[i] = new TreeMap<>();
    }

    public HashTable__1(){
        this(97);
    }

    private int hash(K key){
    	return (key.hashCode() & 0x7fffffff) % M;  // 0111 1111 1111 1111 1111 1111 1111 1111   32位(和int按位与)
        			// 为什么不用math.abs：现在的目的是 让hashcode和hashtable的索引对应起来，起码得能存进去；而abs想返回int的话，负数最小值是会溢出的，此时返回的还是负数本身，所以是会bug的；
    	 //补码按位与可以保证一定得到一个正int值，因为负数的补码可以想象一下，不考虑符号位去掉-0后其实是和正数的补码一一对应的， 这样按位与之后相当于有一半的值都是重叠的，再取余还是重叠的。所以冲突率还是挺高的。。但起码没有上边的bug了；
    } 
//    public static void main(String[] args) {
//		System.out.println(Math.abs(Integer.MIN_VALUE));  //int最大值为2147483647，而MIN_VALUE绝对值2147483648已经溢出，仍然返回原值-2147483648；   计算机里：0+ 1-
//		System.out.println(-2147483647 & 0x7fffffff);  //原码 全1；位运算是补码运算，正数补码即原码 负数是 除符号位 各位取反 末位+1
//		System.out.println(-2147483648 & 0x7fffffff);  //明明去掉符号位只有31位，为什么负数可以多表示一个数呢？  突然想起来了 是因为±0；让全0表示0，多出的100...00来表示-(MAX+1);
//		System.out.println(1 & 0x7fffffff);  //位运算是补码运算，正数补码即原码 
//	}
    
    public int getSize(){
        return size;
    }

    public void add(K key, V value){   //java的接口叫put
        TreeMap<K, V> map = hashtable[hash(key)];
        if(map.containsKey(key))
            map.put(key, value); //此时等价于更新 所以size不变
        else{
            map.put(key, value);
            size ++;
        }
    }

    public V remove(K key){
        V ret = null;
        TreeMap<K, V> map = hashtable[hash(key)];
        if(map.containsKey(key)){
            ret = map.remove(key);
            size --;
        }
        return ret;
    }

    public void set(K key, V value){
        TreeMap<K, V> map = hashtable[hash(key)];
        if(!map.containsKey(key))
            throw new IllegalArgumentException(key + " doesn't exist!");

        map.put(key, value);
    }

    public boolean contains(K key){
        return hashtable[hash(key)].containsKey(key);
    }

    public V get(K key){   //最快是O(1)，最慢也是O(logh)，而hash冲突本来就不会很多，O(logh)是很接近O(1)的
        return hashtable[hash(key)].get(key);
    }
}
